home *** CD-ROM | disk | FTP | other *** search
/ FM Towns: Free Software Collection 9 / FM Towns Free Software Collection 9.iso / t_os / tool / pcom / src / huffman.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  4.8 KB  |  254 lines
  1. #include <stdio.h>
  2. #include <nslib.h>
  3. #include "pc_inc.h"
  4.  
  5. #define EOS            (256)
  6.  
  7.  
  8. static void count( char *src, NODE *node, int n )
  9. {
  10.     int i;
  11.     unsigned int max=0;
  12.  
  13.     _fill_b( node, 0, sizeof( NODE )*514 );
  14.  
  15.     for( i=0; i<n; i++ )
  16.         node[src[i]].cu++;
  17.  
  18.     for( i=0; i<256; i++ )
  19.         if ( node[i].cu > max )
  20.             max = node[i].cu;
  21.  
  22.     for( i=0; i<256; i++ )
  23.         if ( node[i].cu )
  24.             {
  25.             node[i].cu = ( node[i].cu * 255 ) / max;
  26.             if ( node[i].cu == 0 ) node[i].cu++;
  27.             }
  28.     node[EOS].cu = 1;
  29. }
  30.  
  31. static int eq( NODE *node, int n )
  32. {
  33.     int i;
  34.     for( i=1; i<n; i++ ) if ( node[0].cu != node[i].cu ) return ( i );
  35.     return ( n );
  36. }
  37.  
  38. static int movs( char *dest, NODE *node, int *n )
  39. {
  40.     int i, m=127;
  41.  
  42.     if ( *n > 127 )
  43.         { dest[0] = 127; *n -= 127; }
  44.     else
  45.         { dest[0] = (schar)(*n); m = *n; *n = 0; }
  46.  
  47.     for( i=0; i<m; i++ )
  48.         dest[i+1] = (char)node[i].cu;
  49.     return ( m+1 );
  50. }
  51.  
  52. static int putcount( NODE *node, BIT_FILE *bfp )
  53. {
  54.     int i, edi=0, cu=0, eqn=0;
  55.     char buf[512];
  56.  
  57.     for( i=0; i<256; )
  58.         {
  59.         if ( ( eqn = eq( &node[i], 256-i ) ) > 2 )
  60.             {
  61.             while( cu )
  62.                 edi += movs( &buf[edi], &node[i-cu], &cu );
  63.             if ( eqn > 128 )
  64.                 eqn = 128;
  65.             buf[edi++] = -(schar)eqn;
  66.             buf[edi++] = node[i].cu;
  67.             }
  68.         else
  69.             cu += eqn;
  70.         i += eqn;
  71.         }
  72.  
  73.     while( cu )
  74.         edi += movs( &buf[edi], &node[i-cu], &cu );
  75.     if ( BIT_write_bytes( buf, edi, 1, bfp ) < 1 )
  76.         return (-1);
  77.  
  78.     return ( edi );
  79. }
  80.  
  81. static int getcount( NODE *node, BIT_FILE *bfp )
  82. {
  83.     int i;
  84.     schar c, si;
  85.     char d, buf[256];
  86.  
  87.     for( i=0; i<256; )
  88.         {
  89.         if ( BIT_read_bytes( &c, 1, 1, bfp ) < 1 )
  90.             return (-1);
  91.         if ( c < 0 )
  92.             {
  93.             if ( BIT_read_bytes( &d, 1, 1, bfp ) < 1 )
  94.                 return (-1);
  95.             for( ; c; c++, i++ )
  96.                 node[i].cu = (int)d;
  97.             }
  98.         else
  99.             {
  100.             if ( BIT_read_bytes( buf, (int)c, 1, bfp ) < 1 )
  101.                 return (-1);
  102.             for( si=0; si<c; si++, i++ )
  103.                 node[i].cu = (int)buf[si];
  104.             }
  105.         }
  106.     node[EOS].cu = 1;
  107.     return (0);
  108. }
  109.  
  110. static int tree_for_encode( NODE *node )
  111. {
  112.     int next, i, min1, min2;
  113.  
  114.     for( i=0; i<256; i++ )
  115.         if ( node[i].cu == 0 )
  116.             node[i].c0 = i;
  117.  
  118.     node[513].cu = 0xffffffff;
  119.     for( next=EOS+1; ; next++ )
  120.         {
  121.         min1 = min2 = 513;
  122.         for( i=0; i<next; i++ )
  123.             if ( node[i].cu )
  124.                 if ( node[i].cu < node[min1].cu )
  125.                     {
  126.                     min2 = min1;
  127.                     min1 = i;
  128.                     }
  129.                 else if ( node[i].cu < node[min2].cu )
  130.                     min2 = i;
  131.         if ( min2 == 513 )
  132.             break;
  133.         node[next].cu = node[min1].cu + node[min2].cu;
  134.         node[min1].cu = node[min2].cu = 0;
  135.         node[min1].c0 = node[min2].c0 = next;
  136.         node[min1].c1 = 0;
  137.         node[min2].c1 = 1;
  138.         }
  139.     next--;
  140.     node[next].c0 = next;
  141.     return ( next );
  142. }
  143.  
  144. static int tree_for_decode( NODE *node )
  145. {
  146.     int next, i, min1, min2;
  147.  
  148.     node[513].cu = 0xffffffff;
  149.     for( next=EOS+1; ; next++ )
  150.         {
  151.         min1 = min2 = 513;
  152.         for( i=0; i<next; i++ )
  153.             if ( node[i].cu )
  154.                 if ( node[i].cu < node[min1].cu )
  155.                     {
  156.                     min2 = min1;
  157.                     min1 = i;
  158.                     }
  159.                 else if ( node[i].cu < node[min2].cu )
  160.                     min2 = i;
  161.         if ( min2 == 513 )
  162.             break;
  163.         node[next].cu = node[min1].cu + node[min2].cu;
  164.         node[min1].cu = node[min2].cu = 0;
  165.         node[next].c0 = min1;
  166.         node[next].c1 = min2;
  167.         }
  168.     return ( next-1 );
  169. }
  170.  
  171. static void to_code( NODE *node, CODE *code )
  172. {
  173.     int i, cur, bcu;
  174.  
  175.     _fill_b( code, 0, sizeof( CODE )*257 );
  176.     for( i=0; i<257; i++ )
  177.         {
  178.         for( cur=i, bcu=0; node[cur].c0 != cur; cur=node[cur].c0, bcu++ )
  179.             if ( node[cur].c1 )
  180.                 code[i].code |= 1<<bcu;
  181.         code[i].bits = bcu;
  182.         }
  183. }
  184.  
  185. static int encode( char *src, int n, BIT_FILE *bfp, CODE *code )
  186. {
  187.     int i, cu=0;
  188.     unsigned int bits;
  189.  
  190.     for( i=0; i<n; i++ )
  191.         {
  192.         bits = code[src[i]].bits;
  193.         if ( BIT_write_bits( code[src[i]].code, bits, bfp ) < bits )
  194.             return (-1);
  195.         cu += bits;
  196.         }
  197.     bits = code[EOS].bits;
  198.     if ( BIT_write_bits( code[EOS].code, bits, bfp ) < bits )
  199.         return (-1);
  200.     cu += bits;
  201.  
  202.     return ( cu );
  203. }
  204.  
  205. static int decode( char *dest, BIT_FILE *bfp, NODE *node, int root )
  206. {
  207.     int i, nd;
  208.     unsigned int buf;
  209.  
  210.     for( i=0; ; i++ )
  211.         {
  212.         nd = root;
  213.         do    {
  214.             if ( BIT_read_bit( &buf, bfp ) == 0 )
  215.                 return (i);
  216.             if ( buf )
  217.                 nd = node[nd].c1;
  218.             else
  219.                 nd = node[nd].c0;
  220.             }
  221.         while( nd > EOS );
  222.         if ( nd == EOS ) break;
  223.         dest[i] = (char)nd;
  224.         }
  225.     return (i);
  226. }
  227.  
  228. int huff_comp( char *src, int n, BIT_FILE *bfp )
  229. {
  230.     NODE node[514];
  231.     CODE code[257];
  232.     int bytes, ret;
  233.  
  234.     count( src, node, n );
  235.     if ( ( bytes = putcount( node, bfp ) ) == -1 )
  236.         return (-1);
  237.     tree_for_encode( node );
  238.     to_code( node, code );
  239.     if ( ( ret = encode( src, n, bfp, code ) ) == -1 )
  240.         return (-1);
  241.     return ( bytes + (ret+7)/8 );
  242. }
  243.  
  244. int huff_exp( char *dest, BIT_FILE *bfp )
  245. {
  246.     NODE node[514];
  247.     int root;
  248.  
  249.     if ( getcount( node, bfp ) == -1 )
  250.         return (-1);
  251.     root = tree_for_decode( node );
  252.     return ( decode( dest, bfp, node, root ) );
  253. }
  254.